package com.jiang.专题.动态规划.Q1312;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/13 21:58
 */
class Solution {
    // 区间动态规划
    // public int minInsertions(String s) {
    //     int len = s.length();
    //     // 状态转移方程
    //     // dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1) if s[i] != s[j]
    //     // dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1, dp[i + 1][j - 1]) if s[i] == s[j]
    //     int[][] dp = new int[len][len]; // dp[i][j] 表示 下标i~j需添加最少字符
    //     for (int j = 1; j < len; j++) {
    //         for (int i = j - 1; i >= 0; i--) {
    //             dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
    //             if (s.charAt(i) == s.charAt(j)) {
    //                 dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
    //             }
    //         }
    //     }
    //     // for (int span = 2; span <= n; ++span) {
    //     //     for (int i = 0; i <= n - span; ++i) {
    //     //         int j = i + span - 1;
    //     //         dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
    //     //         if (s.charAt(i) == s.charAt(j)) {
    //     //             dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
    //     //         }
    //     //     }
    //     // }
    //     return dp[0][len - 1];
    // }

    // 总体动态规划
    // public int minInsertions(String s) {
    //     int n = s.length();
    //     String t = new StringBuilder(s).reverse().toString();
    //     // 状态转移方程
    //     // dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) if s[i] != s[j]
    //     // dp[i][j] = max(dp[i + 1][j], dp[i][j - 1], dp[i + 1][j - 1] + 1) if s[i] == s[j]
    //     int[][] dp = new int[n + 1][n + 1]; // dp[i][j]表示字符串s的前i个字符和字符串t的前j个字符的最长公共子序列的长度。
    //     for (int i = 1; i <= n; ++i) {
    //         for (int j = 1; j <= n; ++j) {
    //             dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    //             if (s.charAt(i - 1) == t.charAt(j - 1)) {
    //                 dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
    //             }
    //         }
    //     }
    //     return n - dp[n][n];
    // }

    // 递归
    public int minInsertions(String s) {
        int len = s.length();
        char[] arr = s.toCharArray();
        int[][] dp = new int[len][len];
        return dfs(arr, 0, len - 1, dp);
    }

    public int dfs(char[] arr, int i, int j, int[][] dp) {
        int len = arr.length;
        if (i > j) return 0;
        if (dp[i][j] != 0) return dp[i][j];

        if (arr[i] == arr[j]) {
            dp[i][j] = dfs(arr, i + 1, j - 1, dp);
        } else {
            dp[i][j] = Math.min(dfs(arr, i + 1, j, dp), dfs(arr, i, j - 1, dp)) + 1;
        }
        return dp[i][j];
    }
}
